package cn.rocky.structures.trie;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 字典树 实现存放和遍历索引的功能。
 * 与二叉查找树不同, 键不是直接保存在节点中的,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,
 * 也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分
 * 内部节点对应的键才有相关的值。
 *
 * 常见面试题:
 * 1. 简述字典树的数据结构
 * 2. 叙述你怎么来实现一个字典树
 * 3. 字典树的实际业务场景举例【排序、全文搜索、网络搜索引擎、生物信息】
 * 4. 字典树的存入和检索的时间复杂度
 * 5. 还有哪些字典树的实现方式【后缀树 (opens new window)、哈希树 (opens new window)、帽子树 (opens new window)】
 *
 */
public class Trie {

    public final static TrieNode wordsTree = new TrieNode();

    /**
     * insert 方法接收单词和注释信息, 并对一个单词按照char进行拆分,拆分后则计算出索引位置并以此存放。存放完成后标记单词和附属上单词的注释信息。
     */
    public void insert(String words, String explain) {
        TrieNode root = wordsTree;
        char[] chars = words.toCharArray();
        for (char c : chars) {
            int idx = c - 'a'; // - a 从 0 开始，参考 ASCII 码表
            if (root.slot[idx] == null) {
                root.slot[idx] = new TrieNode();
            }
            root = root.slot[idx];
            root.c = c;
            root.prefix++;
        }
        root.explain = explain; // 单词的注释说明信息
        root.isWord = true;     // 循环拆解单词后标记
    }

    public List<String> searchPrefix(String prefix) {
        TrieNode root = wordsTree;
        char[] chars = prefix.toCharArray();
        StringBuilder cache = new StringBuilder();
        // 精准匹配：根据前置精准查找
        for (char c : chars) {
            int idx = c - 'a';
            // 匹配为空
            if (idx > root.slot.length || idx < 0 || root.slot[idx] == null) {
                return Collections.emptyList();
            }
            cache.append(c);
            root = root.slot[idx];
        }
        // 模糊匹配：根据前缀的最后一个单词，递归遍历所有的单词
        ArrayList<String> list = new ArrayList<>();
        if (root.prefix != 0) {
            for (int i = 0; i < root.slot.length; i++) {
                if (root.slot[i] != null) {
                    char c = (char) (i + 'a');
                    collect(root.slot[i], String.valueOf(cache) + c, list, 15);
                    if (list.size() >= 15) {
                        return list;
                    }
                }
            }
        }
        return list;
    }

    protected void collect(TrieNode trieNode, String pre, List<String> queue, int resultLimit) {
        // 找到单词
        if (trieNode.isWord) {
            trieNode.word = pre;
            // 保存检索到的单词到 queue
            queue.add(trieNode.word + " -> " + trieNode.explain);
            if (queue.size() >= resultLimit) {
                return;
            }
        }
        // 递归调用，查找单词
        for (int i = 0; i < trieNode.slot.length; i++) {
            char c = (char) ('a' + i);
            if (trieNode.slot[i] != null) {
                collect(trieNode.slot[i], pre + c, queue, resultLimit);
            }
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        // 存入
        trie.insert("bat","大厂");
        trie.insert("batch", "批量");
        trie.insert("bitch", "彪子");
        trie.insert("battle", "战斗");

        // 检索
        List<String> trieNodes = trie.searchPrefix("ba");
        System.out.println(trieNodes.toString());
    }
}
